package com.structure.algorithm;

/**
 * 快速排序
 * Created by sucre on 2015/11/25.
 */
public class QuickSort {
    private static void quickSorts(int[] sa,int left, int right){
        int i,j,temp,t;
        if(left<right) {
            temp = sa[left];//temp中存的就是基准数
            i = left;
            j = right;
            while (i != j) {
                // 顺序很重要，要先从右往左找
                while (sa[j] >= temp && i < j) {
                    j--;
                }
                // 再从左往右找
                while (sa[i] <= temp && i < j) {
                    i++;
                }
                // 交换两个数在数组中的位置
                if (i < j) {
                    t = sa[i];
                    sa[i] = sa[j];
                    sa[j] = t;
                }
            }
            // 最终将基准数归位
            sa[left] = sa[i];
            sa[i] = temp;
            quickSorts(sa,left,i-1);
            quickSorts(sa,i+1,right);
        }
    }
    public static void main(String[] args){
        int[] sa = new int[]{6,1,2,7,9,3,4,5,10,8};
        quickSorts(sa,0,sa.length-1);
        for(int s:sa){
            System.out.print(s);
        }
    }
}
